home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / agrep / agrep.algorithms < prev    next >
Text File  |  1994-08-01  |  3KB  |  48 lines
  1. The implementation of agrep includes the following algorithms.
  2. Except for exact matching of simple patterns, for which we use 
  3. a simple variation of the Boyer-Moore algorithm, 
  4. all the algorithms (listed below) were designed by Sun Wu and Udi Manber.
  5.  
  6. 1. bitap:  The most general algorithm inside agrep.
  7.        It supports many extensions such as approximate regular expression 
  8.        pattern matching, non-uniform costs, simultaneous matching of 
  9.        multiple patterns, mixed exact/approximate matching, etc.
  10.        The algorithm is described in agrep.ps.1.
  11.  
  12. 2. mgrep:  A sub-linear expect-time algorithm for matching a set of patterns.
  13.        It assumes that the set of patterns contains k patterns, and that
  14.        the shortest pattern is of size m.
  15.        See agrep.ps.2 for a brief description of the algorithm.
  16.  
  17. 3. amonkey: a Boyer-Moore style algorithm for approximate pattern matching.
  18.        let b = log_c (2*m), where c is the size of alphabet set.
  19.        In the preprocessing, a table is built to determine whether
  20.        a given substring of size b is in the pattern.
  21.        Suppose we are looking for matches with at most k errors.
  22.        The search is done in two passes.
  23.        In the first pass (the filtering pass), the areas in the text
  24.        that have a possibility to contain the matches are marked.
  25.        The second pass finds the matches in those marked areas.
  26.        The search in the first pass is done in the following way.
  27.        Suppose the end position of the pattern is currently aligned with 
  28.        position tx in the text.
  29.        The algorithm scans backward from tx until either (k+1) blocks
  30.        that do not occur in the pattern have been scanned, or
  31.        the scan has passed position (tx-m+k).
  32.        In the former case, pattern is shifted forward to align
  33.        the beginning position of the pattern with one character after
  34.        the position in the text where the scan was stopped.
  35.        In the latter case, we marked tx-m to tx+m as a candidate area.
  36.  
  37. 4. mmonkey: Combining the mgrep algorithm with a partition technique, we
  38.        have an algorithm with the same time complexity as amonkey.
  39.        For ASCII text and pattern, this algorithm is faster than amonkey.
  40.        The principle of the partition technique is as follows.
  41.        Let A and B be two strings of size m. 
  42.        If we partition A into (k+1) blocks, then the distance between 
  43.        A and B is > k if none of the blocks of A occur in B. 
  44.        This implies that to match A with no more than k errors, 
  45.        B has to contain a substring that matches exactly one block of A.
  46.        A brief description can be found in agrep.ps.2.
  47.  
  48.